package pro.softzhang.algo.lc900;

import java.util.ArrayList;
import java.util.List;

/**
 * 994. 腐烂的橘子
 * https://leetcode.cn/problems/rotting-oranges
 */
public class LC994_RottingOranges {
    public static void main(String[] args) {

    }

    static
    class Solution {
        private int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        public int orangesRotting(int[][] grid) {
            int m = grid.length, n = grid[0].length;
            int fresh = 0;
            List<int[]> q = new ArrayList<>();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1) {
                        fresh++; // 统计新鲜橘子个数
                    } else if (grid[i][j] == 2) {
                        q.add(new int[]{i, j}); // 一开始就腐烂的橘子
                    }
                }
            }

            int minutes = -1;
            while (!q.isEmpty()) {
                minutes++; // 经过一分钟
                List<int[]> tmp = q;
                q = new ArrayList<>();
                for (int[] pos : tmp) { // 已经腐烂的橘子
                    for (int[] d : DIRS) { // 四方向
                        int i = pos[0] + d[0];
                        int j = pos[1] + d[1];
                        if (0 <= i && i < m && 0 <= j && j < n && grid[i][j] == 1) { // 新鲜橘子
                            fresh--;
                            grid[i][j] = 2; // 变成腐烂橘子
                            q.add(new int[]{i, j});
                        }
                    }
                }
            }

            return fresh > 0 ? -1 : Math.max(minutes, 0);
        }
    }
}
